#include "shellsort.h"

// 构造函数：初始化排序数据并设置初始间隔 gap
ShellSort::ShellSort(const QVector<int> &values)
    : gap(values.size() / 2), // 初始 gap 为数组长度的一半
      i(gap),                 // i 从 gap 开始
      j(0),                   // j 初始为 0（将随后赋为 i）
      sorted(false),
      compareCount(0),
      swapCount(0)
{
    // 初始化 bars 数据（带颜色信息的排序条）
    for (int v : values)
        bars.append({v, Qt::lightGray});
}

// step：执行 Shell 排序的一步（逐步动画执行）
void ShellSort::step() {
    // 如果 gap 已为 0 或已标记为完成，则结束
    if (sorted || gap == 0) {
        sorted = true;
        return;
    }

    // 每步重置所有元素颜色为默认灰色
    for (auto &bar : bars)
        bar.color = Qt::lightGray;

    // 执行当前 gap 情况下的插入排序逻辑
    if (j >= gap &&
        ((sortOrder == SortOrder::Ascending  && bars[j - gap].value > bars[j].value) ||
         (sortOrder == SortOrder::Descending && bars[j - gap].value < bars[j].value)))
    {
        // 标记参与比较的条颜色
        bars[j].color = Qt::red;
        bars[j - gap].color = Qt::green;

        // 执行交换
        std::swap(bars[j], bars[j - gap]);
        swapCount++;
        compareCount++;

        // 继续向前比较 gap 个位置
        j -= gap;
    } else {
        // 当前 j 不满足交换条件，向前推进 i 和 j
        i++;
        j = i;

        // 如果一轮 gap 完成，缩小 gap，重新开始下一轮
        if (i >= bars.size()) {
            gap /= 2;
            i = gap;
            j = i;
        }
    }
}

// 判断是否排序完成
bool ShellSort::isFinished() const {
    return sorted;
}

// 返回当前排序条数据（含颜色）
const QVector<SortBar>& ShellSort::getData() const {
    return bars;
}

// 获取并清除当前 step 中的比较次数
int ShellSort::getAndResetCompareCount() {
    int c = compareCount;
    compareCount = 0;
    return c;
}

// 获取并清除当前 step 中的交换次数
int ShellSort::getAndResetSwapCount() {
    int s = swapCount;
    swapCount = 0;
    return s;
}

// 返回 Shell 排序的时间复杂度信息
QString ShellSort::getComplexityInfo() const {
    return "平均 O(n^1.5)，最好 O(n log n)，最坏 O(n^2)，空间复杂度 O(1)";
}

// 设置排序顺序（升序或降序）
void ShellSort::setOrder(SortOrder order) {
    sortOrder = order;
}
